Let $S$ be a planar $n$-point set. A triangulation for $S$ is a maximal planestraight-line graph with vertex set $S$. The Voronoi diagram for $S$ is thesubdivision of the plane into cells such that all points in a cell have thesame nearest neighbor in $S$. Classically, both structures can be computed in$O(n \log n)$ time and $O(n)$ space. We study the situation when the availableworkspace is limited: given a parameter $s \in \{1, \dots, n\}$, an$s$-workspace algorithm has read-only access to an input array with the pointsfrom $S$ in arbitrary order, and it may use only $O(s)$ additional words of$\Theta(\log n)$ bits for reading and writing intermediate data. The outputshould then be written to a write-only structure. We describe a deterministic$s$-workspace algorithm for computing an arbitrary triangulation of $S$ in time$O(n^2/s + n \log n \log s )$ and a randomized $s$-workspace algorithm forfinding the Voronoi diagram of $S$ in expected time $O((n^2/s) \log s + n \logs \log^*s)$.
展开▼
机译：令$ S $为平面$ n $点集。 $ S $的三角剖分是顶点设置为$ S $的最大平面直线图。 $ S $的Voronoi图是将平面细分为多个像元，使得像元中的所有点在$ S $中具有相同的最近邻点。传统上，两个结构都可以在$ O（n \ log n）$时间和$ O（n）$空间中进行计算。我们研究了可用工作空间受限的情况：给定参数$ s \ in \ {1，\ dots，n \} $，$ s $ -workspace算法对$ S中的点具有输入数组的只读访问权限$以任意顺序，并且它可能仅使用$ \ Theta（\ log n）$位的$ O（s）$个附加字来读取和写入中间数据。然后应将输出写入只写结构。我们描述了一种确定性的$ s $-工作区算法，用于计算时间$ O（n ^ 2 / s + n \ log n \ log s）$中的$ S $的任意三角剖分，以及一种随机的$ s $ -workspace算法来查找预期时间$ O（（n ^ 2 / s）\ log s + n \ logs \ log ^ * s）$的Voronoi图。
展开▼
